home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part2 / 13590 < prev    next >
Encoding:
Text File  |  1996-08-05  |  11.0 KB  |  362 lines
  1. Path: solon.com!not-for-mail
  2. From: Chris Torek <torek@elf.bsdi.com>
  3. Newsgroups: comp.lang.c,comp.lang.c.moderated
  4. Subject: Re: C coding problem
  5. Date: 8 Apr 1996 22:46:58 -0500
  6. Organization: Berkeley Software Design, Inc.
  7. Sender: clc@solutions.solon.com
  8. Approved: clc@solutions.solon.com
  9. Message-ID: <4kcmji$p13@solutions.solon.com>
  10. References: <4j06na$808@solutions.solon.com> <4k1qh3$5hn@solutions.solon.com> <4k5vrk$a2d@solutions.solon.com> <4kbdq6$ec2@solutions.solon.com>
  11. Reply-To: torek@bsdi.com
  12. NNTP-Posting-Host: solutions.solon.com
  13.  
  14. (I have removed a bunch of HP-specific groups.)
  15.  
  16. Someone wrote:
  17. >>>In such and environment, 
  18. >>>    *q++ = *p++;
  19. >>>[can be slower than]
  20. >>>    q[i] = p[i], ++i;
  21.  
  22. In article <4k5vrk$a2d@solutions.solon.com>
  23. schwarz@mips.complang.tuwien.ac.at (Konrad Schwarz) wrote:
  24. >>Note that indexed addressing often works only for small powers of
  25. >>two, e.g., x86 family.
  26.  
  27. In article <4kbdq6$ec2@solutions.solon.com> Verne Arase
  28. <VArase@varase.it.luc.edu> wrote:
  29. >Why only small powers of two? You mean if the size of each element is a
  30. >small power of two (so you can use shift rather than multiply)?
  31.  
  32. The reason that it generally works `only for small powers of two'
  33. for such systems is that the hardware indexed-addressing modes only
  34. support the hardware's datatypes, which typically use 1, 2, 4, and
  35. 8 8-bit bytes.  This is called `scaled indexed addressing': if p
  36. is a `long *', and long is 8 bytes, p[i] might use the `8 byte
  37. scaled index' mode to multiply i by 8 before adding it to p, all in
  38. one instruction.
  39.  
  40. (Incidentally, on machines with rapid scaled index addressing and
  41. `load effective address' instructions, these can often be used to
  42. synthesize multiplication by values such as 3, 5, and 9 in a single
  43. instruction.  GCC will do this for you when possible.  This turns
  44. out to be useful more often you might expect: calculations of the
  45. form `x * 10' are common, and 10 is 2*5, and x*5 is `lea x,x[x,4]'.)
  46.  
  47. >AFAIK, indexed addressing works with just about all CISC computers, from
  48. >the x86 and 68K line through S/360/370/390.
  49.  
  50. There are CISCs that lack indexed addressing, and RISCs that have
  51. it, and on some implementations of some CISC architectures, the
  52. scaled indexing addressing modes are slower than some alternatives.
  53. It is not generally possible to determine the fastest method of
  54. copying memory without a lot more information about the hardware.
  55. (For instance, the SPARC has indexed addressing, but not scaled
  56. indexed addressing, so that the index must be a byte offset.)
  57.  
  58. In article <4k60p9$ahr@solutions.solon.com> falstaff@xs4all.nl disparaged
  59. code of the form:
  60. >void loserstrcpy(char p[],char q[])
  61. >{  int i=0;
  62. >
  63. >   while((q[i]=p[i])!=0)
  64. >      i++;
  65. >}
  66.  
  67. As it happens, however, a literal translation of this code to SPARC
  68. assembly performs better than a literal translation of the pointer
  69. version.
  70.  
  71. Finally, I present here some code I wrote and tested specifically
  72. for a `kernel bcopy' implementation (analagous to the Standard's
  73. memcpy---i.e., does not handle overlap---but lacks a return value).
  74. This is the fastest method I have found yet for the SPARC.  Note
  75. that it uses both indexing and pointer increments, all carefully
  76. chosen based on the target instruction set.  The code is byte-order
  77. dependent and `tuned' for gcc (and yet still requires some minor
  78. hand-tuning afterward, as gcc creates some unnecessary pointers
  79. within the unrolled inner loops).  The fancy alignment network at
  80. the end, while complex, is faster than byte-at-a-time copies, on
  81. the machines I tested.
  82.  
  83. (Note that the alignment network can be recoded for little-endian
  84. machines, even those that do not impose alignment constraints in
  85. hardware.  On the other hand, many of those have specialized
  86. memory-copy instructions (e.g., VAX, x86), are register-poor (x86),
  87. have different relative CPU-to-memory bandwidth, or have some or
  88. all of these and other factors that make it unprofitable.  The MIPS
  89. Rx000, which is either-endian and has hardware alignment constriaints,
  90. has special LWL and LWR instructions for building the left and right
  91. parts, so that this should not be attempted directly in C.)
  92.  
  93. /* prototype bcopy, for turning into assembly... */
  94.  
  95. void
  96. bcopy(void *src0, void *dst0, unsigned int len) {
  97.     char *src = src0, *dst = dst0;
  98.     unsigned int n, i;
  99.     unsigned int lp, rp;    /* left and right partial words */
  100.  
  101.     i = 0;
  102.     n = (int)src | (int)dst;
  103.  
  104.     /*
  105.      * Handle small copies separately.  We *must* handle 6 or fewer
  106.      * bytes here as the fancier code may copy 7 without looking at
  107.      * the length, but we might as well take care of anything under 8.
  108.      */
  109.     if (len < 8) {
  110.         /*
  111.          * Too small to fuss much, but handle 4-aligned-bytes
  112.          * quickly.
  113.          */
  114.         if (len >= 4 && (n & 3) == 0) {
  115.             *(int *)dst = *(int *)src;
  116.             i = 4;
  117.         }
  118.         while (i < len)
  119.             dst[i] = src[i], i++;
  120.         return;
  121.     }
  122.  
  123.     /*
  124.      * We have at least 8 bytes to copy.  Handle easy doubleword
  125.      * copies (everything perfectly aligned) first.
  126.      */
  127.     if ((n & 7) == 0)
  128.         goto copy_doublewords;
  129.  
  130.     /*
  131.      * No matter which algorithm we choose, the destination must be
  132.      * int-aligned.  If it is not even short-aligned, fix that with
  133.      * a one-byte copy now, then choose an alignment algorithm.
  134.      */
  135.     n = (int)src ^ (int)dst;
  136.     if ((int)dst & 1)
  137.         *dst++ = *src++, len--;
  138.     if ((n & 7) == 0) {
  139.         /*
  140.          * Align to doubleword, then copy doublewords.  Move a
  141.          * short and/or an int first, if necessary.  This plus the
  142.          * byte we might have copied above means that len had
  143.          * better be at least 7.
  144.          */
  145.         if ((int)dst & 2)
  146.             *(short *)dst = *(short *)src,
  147.                 dst += 2, src += 2, len -= 2;
  148.         if ((int)dst & 4)
  149.             *(int *)dst = *(int *)src,
  150.                 dst += 4, src += 4, len -= 4;
  151. copy_doublewords:
  152.         /* Copy via ldd/std, with an unrolled inner loop. */
  153.         n = len / 8 / 8;
  154.         if (n) {
  155.             len -= n * 8 * 8;
  156. #define CP(k)    ((long long *)dst)[k] = ((long long *)src)[k]
  157.             do {
  158.                 CP(0); CP(1); CP(2); CP(3);
  159.                 CP(4); CP(5); CP(6); CP(7);
  160.                 dst += 8 * 8, src += 8 * 8;
  161.             } while (--n > 0);
  162. #undef CP
  163.         }
  164.  
  165.         /* Handle any trailing `long long's. */
  166.         n = len & ~7;
  167.         while (i < n)
  168.             *(long long *)&dst[i] = *(long long *)&src[i], i += 8;
  169.  
  170.         /* Mop up trailing int, short, and/or byte. */
  171.         if ((n = len - i) == 0)
  172.             return;
  173.         if (n >= 4) {
  174.             *(int *)&dst[i] = *(int *)&src[i], i += 4;
  175.             goto trailing_check;
  176.         }
  177.         goto trailing_123;
  178.     }
  179.  
  180.     if ((n & 3) == 0) {
  181.         /*
  182.          * Align to int, then copy ints.  This is just like the
  183.          * doubleword loop, but moves only four bytes at a crack.
  184.          */
  185.         if ((int)dst & 2)
  186.             *(short *)dst = *(short *)src,
  187.                 dst += 2, src += 2, len -= 2;
  188.  
  189.         n = len / 4 / 8;
  190.         if (n) {
  191.             len -= n * 4 * 8;
  192. #define CP(k)    ((int *)dst)[k] = ((int *)src)[k]
  193.             do {
  194.                 CP(0); CP(1); CP(2); CP(3);
  195.                 CP(4); CP(5); CP(6); CP(7);
  196.                 dst += 4 * 8, src += 4 * 8;
  197.             } while (--n > 0);
  198. #undef CP
  199.         }
  200.         n = len & ~3;
  201.         while (i < n)
  202.             *(int *)&dst[i] = *(int *)&src[i], i += 4;
  203. trailing_check:
  204.         if ((n = len - i) == 0)
  205.             return;
  206. trailing_123:
  207.         if (n >= 2) {
  208.             /* 2 or 3 bytes left */
  209.             *(short *)&dst[i] = *(short *)&src[i];
  210.             if (n == 2)
  211.                 return;
  212.             i += 2;
  213.         }
  214.         dst[i] = src[i];
  215.         return;
  216.     }
  217.  
  218.     /*
  219.      * Cannot even int-align, but still have at least 7 bytes to copy,
  220.      * and dst is at least short-aligned.  Copy up to two more bytes
  221.      * to make it int-aligned, leaving at least 5 bytes to go.  This
  222.      * will leave src unaligned with a 1, 2, or 3-byte offset.
  223.      *
  224.      * This code is rather complex; see the pictures below for operation.
  225.      */
  226.     if ((int)dst & 3) {
  227.         *dst++ = *src++;
  228.         len--;
  229.         if ((int)dst & 3) {
  230.             *dst++ = *src++;
  231.             len--;
  232.         }
  233.     }
  234.     n = len / 4;        /* n >= 1 */
  235.     if (((int)src & 3) == 1) {
  236.         /*
  237.          *           src               dst
  238.          *    +---------------+    +---------------+
  239.          *    |   | 0 | 1 | 2 |    | 0 | 1 | 2 | 3 |
  240.          *    +---------------+    +---------------+
  241.          *    | 3 | . | . | . |    | . | . | . | . |
  242.          *    +---------------+    +---------------+
  243.          *    | . | w | x | y |    | w | x | y | z |
  244.          *    +---------------+    +---------------+
  245.          *    | z | ? | ? | ? |    | ? | ? | ? |   |
  246.          *    +---------------+    +---------------+
  247.          *
  248.          * (where `.'s repeat as needed and `z' is the last of
  249.          * the fullword-at-dst bytes).  The `empty' slots always
  250.          * exist at src, but need not exist at dst, and we may
  251.          * may need to write none, one, two, or all three of the
  252.          * bytes marked `?' (depending on the leftover length).
  253.          */
  254.         /* Pick up the first three bytes, discarding -1st byte. */
  255.         lp = *(int *)&src[-1] << 8, src += 3;
  256.         do {
  257.             /* lp contains 3 `left hand' bytes */
  258.             rp = *(int *)&src[i];
  259.             /* now rp has `right hand' byte in top nibble */
  260.             *(int *)&dst[i] = lp | (rp >> 24);
  261.             lp = rp << 8;
  262.             i += 4;
  263.         } while (--n > 0);
  264.         /* Up to 3 bytes remain; they are available in lp. */
  265.         if ((len -= i) != 0) {
  266.             if (len == 1)
  267.                 dst[i] = lp >> 24;
  268.             else if (len == 2)
  269.                 *(short *)&dst[i] = lp >> 16;
  270.             else {
  271.                 *(short *)&dst[i] = lp >> 16;
  272.                 dst[i + 2] = lp >> 8;
  273.             }
  274.         }
  275.     } else if (((int)src & 3) == 2) {
  276.         /*
  277.          *           src               dst
  278.          *    +---------------+    +---------------+
  279.          *    |   |   | 0 | 1 |    | 0 | 1 | 2 | 3 |
  280.          *    +---------------+    +---------------+
  281.          *    | 2 | 3 | . | . |    | . | . | . | . |
  282.          *    +---------------+    +---------------+
  283.          *    | . | . | w | x |    | w | x | y | z |
  284.          *    +---------------+    +---------------+
  285.          *    | y | z | ? | ? |    | ? | ? | ? |   +
  286.          *    +---------------+    +---------------+
  287.          *    | ? |
  288.          *    +---+
  289.          *
  290.          * Note that this time we may have to fetch one last
  291.          * byte (the third `?') from src when the full-word
  292.          * loop is done.
  293.          */
  294.         /* Pick up the first two bytes. */
  295.         lp = *(unsigned short *)&src[0] << 16, src += 2;
  296.         do {
  297.             /* lp contains 2 `left hand' bytes */
  298.             rp = *(int *)&src[i];
  299.             /* now rp has two `right hand' bytes */
  300.             *(int *)&dst[i] = lp | (rp >> 16);
  301.             lp = rp << 16;
  302.             i += 4;
  303.         } while (--n > 0);
  304.         /* Up to 3 bytes remain, but only 2 are in lp. */
  305.         if ((len -= i) != 0) {
  306.             if (len == 1)
  307.                 dst[i] = lp >> 24;
  308.             else if (len == 2)
  309.                 *(short *)&dst[i] = lp >> 16;
  310.             else {
  311.                 *(short *)&dst[i] = lp >> 16;
  312.                 rp = src[i];
  313.                 i += 2;
  314.                 dst[i] = rp;
  315.             }
  316.         }
  317.     } else /* (((int)src & 3) == 3) */ {
  318.         /*
  319.          *           src               dst
  320.          *    +---------------+    +---------------+
  321.          *    |   |   |   | 0 |    | 0 | 1 | 2 | 3 |
  322.          *    +---------------+    +---------------+
  323.          *    | 1 | 2 | 3 | . |    | . | . | . | . |
  324.          *    +---------------+    +---------------+
  325.          *    | . | . | . | w |    | w | x | y | z |
  326.          *    +---------------+    +---------------+
  327.          *    | x | y | z | ? |    | ? | ? | ? |   |
  328.          *    +---------------+    +---------------+
  329.          *    | ? | ? |
  330.          *    +---+---+
  331.          *
  332.          * Now we may have to read one or two last bytes from src
  333.          * when the full-word loop is done.
  334.          */
  335.         lp = *src++ << 24;
  336.         do {
  337.             rp = *(int *)&src[i];
  338.             /* now rp has three `right hand' bytes */
  339.             *(int *)&dst[i] = lp | (rp >> 8);
  340.             lp = rp << 24;
  341.             i += 4;
  342.         } while (--n > 0);
  343.         /* Up to 3 bytes remain, but only one is in lp. */
  344.         if ((len -= i) != 0) {
  345.             if (len == 1)
  346.                 dst[i] = lp >> 24;
  347.             else {
  348.                 rp = *(unsigned short *)&src[i];
  349.                 lp |= rp << 8;
  350.                 *(short *)&dst[i] = lp >> 16;
  351.                 if (len == 3) {
  352.                     i += 2;
  353.                     dst[i] = rp /* lp >> 8 */;
  354.                 }
  355.             }
  356.         }
  357.     }
  358. }
  359. -- 
  360. In-Real-Life: Chris Torek, Berkeley Software Design Inc
  361. El Cerrito, CA    Domain:    torek@bsdi.com    +1 510 234 3167
  362.